#include <iostream>
#include <vector>
using namespace std;

class Solution2 {
private:
    vector<int> memo;
    int breakInteger(int n){
        if (n == 1)
            return 1;
        if (memo[n] != -1)
            return memo[n];
        int res = -1;
        for (int i = 1; i <= n-1; i++) {
            res = max(i*(n-i), max(res, i * breakInteger(n - i)));
        }
        memo[n] = res;
        return res;
    }
public:
    int integerBreak(int n) {
        memo = vector<int>(n+1, -1);
        return breakInteger(n);
    }
};

class Solution {
private:
    vector<int> memo;
    int breakInteger(int n){
        if (n == 1)
            return 1;
        if (memo[n] != -1)
            return memo[n];
        int res = -1;
        for (int i = 1; i <= n-1; i++) {
            res = max(i*(n-i), max(res, i * breakInteger(n - i)));
        }
        memo[n] = res;
        return res;
    }
public:
    int integerBreak(int n) {
        memo = vector<int>(n+1, -1);
        return breakInteger(n);
    }
};
int main() {
    int i = Solution().integerBreak(50);
    cout << "Test Answer " << i << endl;
//    std::cout << "Hello, World!" << std::endl;
    return 0;
}